package newBee.class2;

/**
 * https://leetcode.cn/problems/dui-lie-de-zui-da-zhi-lcof/
 * 设计自主结算系统
 */
public class Code02_checkout {
    public static void main(String[] args) {
        Checkout checkout = new Checkout();
        checkout.add(4);
        checkout.add(7);
        int max = checkout.get_max();
        System.out.println("max = " + max);
        int remove = checkout.remove();
        System.out.println("remove = " + remove);
        int max2 = checkout.get_max();
        System.out.println("max = " + max2);

    }

    private static class Checkout {

        private int[] deque;
        private int[] queque;
        private int h;
        private int t;
        private int l;
        private int r;

        public Checkout() {
            this.deque = new int[10000];
            this.queque = new int[10000];
            this.h = this.t = 0;
            this.l = this.r = 0;
        }

        public int get_max() {
            return h == t ? -1 : queque[deque[h]];
        }

        public void add(int value) {
            // 将单调队列中 <=value 的全部出队列
            while (h < t && queque[deque[t - 1]] <= value) {
                t--;
            }
            queque[r] = value;// 数值进入队列
            deque[t++] = r++; // 索引进入最大
        }

        public int remove() {
            if (l == r) return -1;

            int k = queque[l];
            // l: 是队列 queque 的头指针，表示正在移除的元素的位置。
            // deque[h]: 指向的是原队列 queque 中最大值的索引。
            // l > deque[h] 这一条件是为了检查被移除的元素是否正是 deque[h] 所指向的元素，即当前窗口的最大值。如果是，那么就需要更新 deque 的头指针 h
            if (l == deque[h]) {
                //如果条件成立，说明当前窗口移除的元素就是窗口的最大值（deque[h] 指向的元素），那么我们需要调整 deque 的头指针 h，将其向后移动，跳过这个最大值的索引。
                // 这样就保证了 deque[h] 始终指向当前窗口的最大值。
                h++;
            }
            l++;
            return k;
        }
    }

}
